Search engines are a commonly used tool for identifying desired documents from large electronic document collections, including the world-wide internet and internal corporate networks. Documents are often identified by providing the search engine with a search query composed of one or more keywords. The search engine then returns documents matching the search query keywords.
One of the problems in searching a large document collection, such as the billions of documents accessible via the world-wide Internet, is responding to a search query in a reasonable amount of time. Preferably, a search engine can provide an answer to a search query in seconds or less. One technique for improving response time is to store the results or query answers for frequently used search queries in a memory cache. However, responding to a search query with a stored query answer may provide a user with “stale” results that do not include the most relevant documents. A conventional solution is to discard all stored query answers when new information becomes available. This avoids having stale results, but can cause unacceptably long response times as once the stored query answers are discarded, every unique query received will require formation of a new query answer.
Due to the large number of potential search queries, storing search query answers also poses significant problems. The large amount of data makes it difficult to store all of the search query answers on a single machine. Additionally, even if the results could be stored on a single machine, the number of search queries submitted could overwhelm the machines processing capacity, resulting in slow response times. One solution is to split the storage across many machines or memory devices. However, using many machines to store the query answers increases the likelihood that a query answer will become unavailable due to a machine failure. Additionally, response times can still be slow if the query answers are not distributed evenly among the machines.
What is needed is a fault-tolerant method for providing a query answer in response to a query. The method should provide current information in response to a query while maintaining fast response times. The method should also allow for storage of query answers on a plurality of machines while balancing the number of results stored on each machine. The method should also be adaptable to changes in the number of machines currently available for balancing.